/***************************************************
 * @Author: OBKoro1
 * @Create: 2021-02-21
 * @LastEditors: OBKoro1
 * @LastEditTime: 2021-02-21
 * @FilePath: \leetcode-exercise\37-解数独\test.c
 ****************************************************/

#define S 3       // 3x3 宫
#define N (S * S) // 9x9 数独
// 使用三个HASH数组(行、列、宫)来标识数字是否出现过
int rowUsed[N][N] = {0};
int colUsed[N][N] = {0};
int boxUsed[N][N] = {0};
int map[N][N] = {0};
int find = 0;
// 初始化数组标记
void initUsedArr()
{
    memset(rowUsed, 0, sizeof(rowUsed));
    memset(colUsed, 0, sizeof(colUsed));
    memset(boxUsed, 0, sizeof(boxUsed));
    memset(map, 0, sizeof(map));
    return;
}

void addNumber(int val, int row, int col)
{
    // 转化成子矩阵位置
    int idx = (row / S) * S + col / S;
    // 标明row 行存放了 val数字，注意数字对齐的是0，要减去1
    rowUsed[row][val]++;
    // 标明col 列存放了 val数字
    colUsed[col][val]++;
    // 标明子矩阵位置存在val数字
    boxUsed[idx][val]++;
    return;
}

void DelNumber(int val, int row, int col)
{
    // 转化成子矩阵位置
    int idx = (row / S) * S + col / S;
    // 标明row 行移除了 val数字,注意数字对齐的是0，要减去1
    rowUsed[row][val]--;
    // 标明col 列移除了 val数字
    colUsed[col][val]--;
    // 标明子矩阵位置移除val数字
    boxUsed[idx][val]--;
}

// 判断row行，col列能否放置val数字，满足条件1，2，3排查
bool couldfill(int val, int row, int col)
{
    int idx = (row / S) * S + col / S;
    return (rowUsed[row][val] + colUsed[col][val] + boxUsed[idx][val]) == 0;
}

void board2map(char **board)
{
    int row;
    int col;
    int num;
    for (row = 0; row < N; row++)
    {
        for (col = 0; col < N; col++)
        {
            if (board[row][col] != '.')
            {
                num = board[row][col] - '0';
                addNumber(num - 1, row, col);
                map[row][col] = num;
            }
        }
    }
    return;
}

void map2board(char **board)
{
    int row;
    int col;
    for (row = 0; row < N; row++)
    {
        for (col = 0; col < N; col++)
        {
            board[row][col] = map[row][col] + '0';
        }
    }
    return;
}

void DFS(int idx)
{
    int row, col;
    int num, i;

    // 说明找到对应的结果,DFS结束
    if ((find != 0) && (idx == N * N))
    {
        return false;
    }
    // 说明第一次找到结果，DFS结束，数独结果唯一
    if ((idx == N * N) && (find == 0))
    {
        find = 1;
        return true;
    }
    row = idx / N;
    col = idx % N;
    // 该位置已经被占据
    if (map[row][col] != 0)
    {
        return DFS(idx + 1);
    }
    else
    {
        for (num = 1; num <= N; num++)
        {
            if (couldfill(num - 1, row, col) == true)
            {
                addNumber(num - 1, row, col);
                map[row][col] = num;
                if (DFS(idx + 1) == true)
                {
                    return true;
                }
                else
                {
                    // 状态回退
                    map[row][col] = 0;
                    DelNumber(num - 1, row, col);
                }
            }
        }
    }
    return false;
}
void solveSudoku(char **board, int boardSize, int *boardColSize)
{
    initUsedArr();
    board2map(board);
    find = 0;
    DFS(0);
    map2board(board);
    return;
}